// Copyright 2013 By Jshi. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package binary_search

func BinarySearch(n int, cmp func(int) int) int {
	lo, hi := 0, n
	for {
		mi := lo + (hi-lo)/2
		eq := cmp(mi)

		if eq > 0 {
			lo = mi + 1
		} else if eq < 0 {
			hi = mi
		} else {
			return mi
		}

		if lo >= hi {
			return -1 // Not found.
		}
	}
}

func BinarySearchInts(ints []int, x int) int {
	return BinarySearch(len(ints), func(i int) int {
		return x - ints[i]
	})
}
